package Midium;

//29.两数相除
public class Solution29 {
    //超时解法
    public static int _divide(int dividend, int divisor) {
        if (dividend == 0)
            return 0;
        boolean minusSign = false;
        //由题可知，被除数和除数以及结果均为32位有符号整数，因此存在特殊情况，使得结果溢出
        //特殊情况 -2147483648/-1时，最后一次while循环时2147483647+1=2147483648（溢出了，系统会把他当做-2147483648），溢出时应返回2147483647
        if (dividend == -2147483648 && divisor == -1)
            return 2147483647;
        if (dividend == -2147483648 && divisor == 1)
            return -2147483648;
        if ((dividend > 0 && divisor > 0)) {
            dividend = (-1) * dividend;
            divisor = (-1) * divisor;
        } else if (dividend > 0 && divisor < 0) {
            minusSign = true;
            dividend = (-1) * dividend;
        } else if (dividend < 0 && divisor > 0) {
            minusSign = true;
            divisor = (-1) * divisor;
        }
        int res = 0;
        while (dividend <= divisor) {
            if (res == 2147483647)
                return 2147483647;
            res++;
            dividend -= divisor;
        }
        if (minusSign)
            res = res * (-1);
        return res;
    }


    //答案思路:
    //每次让被除数翻倍 比如13>=3 首先计数为1，然后13>=6,计数为2，13>=12，计数为4，13<24,计数不更新
    public static int divide(int dividend, int divisor) {
        if (dividend == -2147483648 && divisor == -1)
            return 2147483647;
        if (dividend == -2147483648 && divisor == 1)
            return -2147483648;
        if (dividend == 0)
            return 0;
        if (dividend == divisor)
            return 1;
        boolean minusSign = false;
        if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
            dividend = dividend < 0 ? dividend : (-1) * dividend;
            divisor = divisor < 0 ? divisor : (-1) * divisor;
            minusSign = true;
        }
        int sum = 1;
        int k = divisor;
        if (dividend > 0 && divisor > 0) {
            //两个数都大于0
            if (dividend < divisor)
                return 0;
            if (divisor << 1 < 0)
                return 1;
            divisor = divisor << 1;
            boolean b = false;
            while (dividend >= divisor) {
                sum = sum << 1;
                if (divisor << 1 < 0) {//防止放大一倍以后变成负数
                    b = true;
                    break;
                }
                divisor = divisor << 1;
            }
            if (sum > 1) {
                divisor = divisor >> 1;
                if (b) {
                    b = false;
                    divisor = divisor << 1;
                }
                divisor += k;
                if (divisor < 0)
                    return sum;
                while (dividend >= divisor) {
                    sum += 1;
                    divisor += k;
                    if (divisor < 0)
                        break;
                }
            }
        } else {
            //两个数都小于0
            //eg.-35和-5，-35<=-5,计数为1，然后-35<=-10,计数为2，-35<=-20,计数为4，
            // -35>-40,计数不更新，然后从-20开始一个一个加-5

            if (dividend > divisor)
                return 0;
            if (divisor << 1 >= 0)
                return minusSign?-1:1;
            divisor = divisor << 1;
            boolean b = false;
            while (dividend <= divisor) {
                sum = sum << 1;
                if (divisor << 1 >= 0) {//防止放大一倍以后变成正数
                    b = true;
                    break;
                }
                divisor = divisor << 1;
            }
            if (sum > 1) {
                divisor = divisor >> 1;
                if (b) {
                    b = false;
                    divisor = divisor << 1;
                }
                divisor += k;
                if (divisor >= 0)
                    return minusSign?(-1) * sum:sum;
                while (dividend <= divisor) {
                    sum += 1;
                    divisor += k;
                    if (divisor >= 0)
                        break;
                }
            }

        }
        if (minusSign)
            return sum * (-1);
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(divide(1100540749, -1090366779));
    }
}
